#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

public class tmp
{
    public tmp() {
        // 写的真的很好
        for (int left = 0; left < nums.length - 2; ++left)
        {
            if (left > 0 && nums[left] == nums[left-1]) continue;        // filter same left

            int mid = left+1;
            int right = nums.length-1;
            while (mid < right)
            {
                if (nums[left] + nums[mid] + nums[right] < target)      // sum < target
                {
                    // 先 mid += 1, 再 filter same, 避免了 mid 和 left相同的情况.
                    ++mid;
                    while(nums[mid] == nums[mid-1] && mid < right) ++mid;   // filter same mid
                }
                else                                                    // sum >= target
                {
                    if(nums[left] + nums[mid] + nums[right] > target)   // sum > target
                    {
                        --right;
                        while(nums[right] == nums[right+1] && mid < right) --right; // filter same right
                    }
                    else                                                // sum == target
                    {
                        result.add(Arrays.asList(nums[left], nums[mid], nums[right]));
                        ++mid;
                        --right;
                        while(nums[mid] == nums[mid-1] && mid < right) ++mid;
                        while(nums[right] == nums[right+1] && mid < right) --right;
                    }
                }
            }
        }
    }
}


"""


class Solution:
    """
    @param numbers: Give an array numbers of n integer
    @return: Find all unique triplets in the array which gives the sum of zero.
    """
    def threeSum(self, numbers):
        if not numbers:
            return []

        self.ret = []
        self.numbers = numbers
        numbers.sort()
        # print('sorted %s' % numbers)
        if numbers[0] > 0:
            return []

        self.l = len(numbers)

        for left in range(0, self.l-2):
            if left > 0 and numbers[left] == numbers[left-1]: continue      # filter same left
            target = 0 - numbers[left]
            self.left = left
            mid = left + 1
            right = self.l - 1
            self.converge_mid_right(mid, right, target)

        return self.ret

    def converge_mid_right(self, mid, right, target):
        # print('conv: ', self.left, mid, right, target)
        while mid < right:
            # NOTE if  mid > self.left + 1      # mid 只和第一个mid比较
            if mid > self.left + 1 and self.numbers[mid] == self.numbers[mid-1]:
                mid += 1
                continue

            if self.numbers[mid] + self.numbers[right] < target:
                mid += 1
                continue
            else:
                # print('converge_right : %s, %s, %s, %s' % (self.left, mid, right, target-self.numbers[mid]))
                self.converge_right(mid, right, target - self.numbers[mid])
                mid += 1

    def converge_right(self, mid, right, target):
        # assert self.numbers[mid] + self.numbers[right] >= target
        # print(self.left, mid, right, target)
        while right > mid:
            if right < self.l-1 and self.numbers[right] == self.numbers[right+1]:
                right -= 1
                continue

            if self.numbers[right] > target:
                right -= 1
                continue
            if self.numbers[right] < target:
                break

            # self.ret.append([self.left, mid, right])
            self.ret.append([self.numbers[self.left], self.numbers[mid], self.numbers[right]])
            right -= 1


def main():
    print("start main")
    s = Solution()
    # ret = s.threeSum([1,0,-1,-1,-1,-1,0,1,1,1])
    # ret = s.threeSum( [-2,-3,-4,-5,-100,99,1,4,4,4,5,1,0,-1,2,3,4,5])
    ret = s.threeSum( [-2, -2, 4, -1, 3])

    print(ret)

if __name__ == "__main__":
    main()
